题目分析

这个面试题还是有一定难度的，虽然能够想到使用栈来计算数学运算问题，但是如何操作栈是本题的一个难点。

栈

本题难以顺序遍历元素，因为遍历到?之后，无法判断后面的那个元素是否仍为一个三目表达式。但是如果从后向前遍历元素，遇到？说明后面的元素都已经计算完毕了。直接判断问号前面的元素为T还是F即可。

如果是T，弹出前面刚刚入栈的?，获取栈顶元素(true对应的表达式1)，再弹出:和栈顶元素(false对应的表达式2)。

如果是F，弹出?，栈顶元素(true对应的表达式1)和:，获取栈顶元素(false对应的表达式2)。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

import java.util.Stack;

public class Solution {
    public char calc(String str) {
        Stack<Character> stack = new Stack<>();
        boolean judge = false;
        for (int i = str.length() - 1; i >= 0; i--) {
            char ch = str.charAt(i);
            if (judge) {
                ch = getChar(stack, ch == 'T');
                judge = false;
            }
            if (ch == '?') {
                judge = true;
            }
            stack.add(ch);
        }
        return stack.peek();
    }

    private char getChar(Stack<Character> stack, boolean judge) {
        stack.pop();
        char res;
        if (judge) {
            res = stack.pop();
            stack.pop();
            stack.pop();
        } else {
            stack.pop();
            stack.pop();
            res = stack.pop();
        }
        return res;
    }
}

刷题总结

这个题目也算是栈类型的困难题了，虽然思路清晰，但是和括号匹配问题不相同，括号匹配问题是从前往后遍历，遇到右括号就弹出左括号。而该题是从后往前遍历，不像传统得栈问题，所以一再强调的要小伙伴们多看一些题目，这样出现一些奇怪的题目，才有可能找到合适的算法。